(Last Mod: 27 November 2010 21:38:01 )
In most applications where a Galois field is employed it is of the form GF(2n). The main reason is convenience. Since math on the polynomial coefficients is done in GF(2), the operations can be converted to binary logic circuits very readily. Furthermore, since there are exactly 2n symbols, those symbols can be represented by the 2n possible bit patterns in an n-bit word. However, these conveniences can mask some of the subtler points of Galois Fields and so this page will work with a slightly more complex Galois Field, namely GF(32), in order to make some of those points more apparent.
It is assumed that the you have either worked through the page on Polynomial Arithmetic in GF(pn) or you will be doing so in parallel with this page. To make this easier, this page is laid in a similar fashion.
Recall from the discussion of finite fields, that a finite field is an algebra consisting of a set of elements and two operators that act on those elements. We are free to define the elements and the operators in any way we choose provided the properties required of a finite field are satisfied. Those requirements are:
Further recall that to be an abelian group, the following properties must hold with respect to the operator:
There are nine symbols in GF(32) which we can represent as the following polynomials:
Elementary Polynomials in GF(32)
| Symbol | Polynomial |
| 00 | 0 |
| 01 | 1 |
| 02 | 2 |
| 10 | D |
| 11 | D+1 |
| 12 | D+2 |
| 20 | 2D |
| 21 | 2D+1 |
| 22 | 2D+2 |
We also need a "primitive polynomial" which, for GF(pn) is a polynomial of order n that cannot be evenly divided by a polynomial of degree less than n. We do not consider the cases for dividing the candidate polynomial by 0 or 1 for obvious reasons (division by 0 is undefined and division by 1 is always possible).
Since primitive polynomials must be irreducible, the high order coefficient must be one and the constant coefficient must be non-zero. In GF(32) this leaves us with only the following six candidates.
Candidate Primitive Polynomials in GF(32)
| Symbol | Polynomial |
| 101 | D2 + 1 |
| 102 | D2 + 2 |
| 111 | D2 + D+1 |
| 112 | D2 + D+2 |
| 121 | D2 + 2D+1 |
| 122 | D2 + 2D+2 |
We could examine each of the candidate polynomials in turn and divide it by each of the potentially irreducible polynomials of order less than n, of which there are only two.
Lower Order Irreducible Polynomials <2 in GF(32)
| Symbol | Polynomial |
| 11 | D+1 |
| 12 | D+2 |
With so few candidates for primitive polynomials and so few lower order irreducible polynomials to work with, an exhaustive search of the space is very straightforward. We will examine three candidates using this approach before turning to the other approach.
Example: Is 101 (D2 + 1) a primitive polynomial in GF(32)
- Dividing D2 + 1 by D + 1 yields D + 2 with a remainder of 2.
- Dividing D2 + 1 by D + 2 yields D + 1 with a remainder of 2.
Since both have non-zero remainders, D2 + 1 is an irreducible polynomial.
The question now is whether D2 + 1 is primitive.
One way to show this is that the smallest value for which D2 + 1 evenly divides Dm - 1 is m = pn - 1 = 8.
A comparable way is to show that Dk generates all of the polynomials in the set. We will pursue this latter course.
k Dk Polynomial Symbol 0 D0 1 01 1 D1 D 10 2 D2 2 02 3 D3 2D 20 4 D4 1 01 5 D5 D 10 6 D6 2 02 7 D7 2D 20 8 D8 1 01 As can be seen, not all of the polynomials in the set are generated as evidenced by D4 generating 1 again and hence creating a cycle of generated polynomials with period of 4. So, while D2 + 1 divides D8 - 1, also also divides D4 - 1.
Therefore, 101 (D2 + 1) is not a primitive polynomial in GF(32).
Example: Is 102 (D2 + 2) a primitive polynomial in GF(32)
- Dividing D2 + 2 by D + 1 yields D + 2 with no remainder.
Hence D2 + 2 is reducible and need not be explored further.
Therefore, 102 (D2 + 2) is not a primitive polynomial in GF(32).
Example: Is 112 (D2 + D + 1) a primitive polynomial in GF(32)
- Dividing D2 + D + 2 by D + 1 yields D with a remainder of 2.
- Dividing D2 + D + 2 by D + 2 yields D + 2 with a remainder of 1.
Since both have non-zero remainders, D2 + D + 2 is an irreducible polynomial.
The question now is whether D2 + D + 2 is primitive. As before, we will see if Dk generates the entire set under this modulus.
k Dk Polynomial Symbol 0 D0 1 01 1 D1 D 10 2 D2 2D + 1 21 3 D3 2D + 2 22 4 D4 2 02 5 D5 2D 20 6 D6 1D + 2 12 7 D7 D + 1 11 8 D8 1 01 As can be seen, all of the polynomials in the set are generated, as evidenced by D8 being the first time (after D0) that 1 is generated.
Therefore, 112 (D2 + D + 2) is a primitive polynomial in GF(32).
The other approach is to finding the irreducible polynomials is to first produce a list of all of the candidate degree-n primitive polynomials and then multiply all of the lower degree polynomials together to produce all of the non-irreducible polynomials of degree n and eliminate these from the list. The initial list is the same as in the previous approach, namely:
Candidate Primitive Polynomials in GF(32)
| Symbol | Polynomial |
| 101 | D2 + 1 |
| 102 | D2 + 2 |
| 111 | D2 + D+1 |
| 112 | D2 + D+2 |
| 121 | D2 + 2D+1 |
| 122 | D2 + 2D+2 |
In the case of n=2, the polynomials of degree less than n can be written in the form
aD + b
Multiplying two such polynomials together, our candidate primitive polynomials may be written in the form
P = (aD + b)(cD + d)
P = (ac)D2 + (ad+bc)D + (bd)
If we were to approach this blindly, we would have to examine 81 possibilities. However, we note that since primitive polynomials must be of order n, that neither a nor c may be zero. This immediately reduces the search space to 36. We also know that the order n coefficient must be exactly 1 which means that a and c must be multiplicative inverses of each other in GF(3). But we have also established that if the high order coefficient is anything greater than 1 that the polynomial is reducible, hence we can restrict our examination to lower order polynomials having an high order coefficient of 1. This means that a and c must both be exactly 1 which simplifies the form of our primitive polynomials to:
P = (D + b)(D + d)
P = D2 + (d+b)D + (bd)
This collapses our search space to only 9 entries and if we impose the requirement that primitive polynomials must have a non-zero constant term then we have reduced it to 4. While this is already quite manageable, we can reduce it even further my nothing that multiplication in any field is commutative and therefore if we order the elements of our set (in any way we choose) then we can limit ourselves to only evaluating those expressions in which the second factor is greater than or equal to the first factor. The result is that we now only have to evaluate 3 expressions. Notice that a little bit of thought up front has saved us 96% of the work.
Candidate Primitive Polynomials that are Reducible in GF(32)
| b | d | b+d | bd | P | symbol |
| 1 | 1 | 2 | 1 | D2+2D+1 | 121 |
| 1 | 2 | 0 | 2 | D2+2 | 102 |
| 2 | 2 | 1 | 1 | D2+D+1 | 111 |
After eliminating these from the original list, we now have the complete list of polynomials of degree n that are irreducible. There are now only three remainingcandidates for being primitive polynomials in GF(32):
Irreducible Candidates for Primitive Polynomials in GF(32)
| Symbol | Polynomial |
| 101 | D2 + 1 |
| 112 | D2 + D+2 |
| 122 | D2 + 2D+2 |
The only remaining task is to see which of these three is/are actually primitive. We have the same tools as with the prior approach and might as well note that two of the three (101 and 112) were evaluated previously with the result that 101 is not primitive while 112 is. At this point we could either go ahead and check 122 to see if it is primitive or we could check how many primitive polynomials there are in GF(32) and let that guide us. Let's do both.
In GF(32), the number of primitive polynomials is exactly given by
N = totient(pn-1)/n = 2
Since there are exactly two primitive polynomials and since we have identified only one and have only one candidate remaining, we can conclude that 122 should be a primitive polynomial; iif it isn't, then we know we have made an error somewhere. We will now verify that 122 is, indeed, primitive by seeing if it generates the entire set of polynomials under this modulus.
| k | Dk | Polynomial | Symbol |
| 0 | D0 | 1 | 01 |
| 1 | D1 | D | 10 |
| 2 | D2 | D + 1 | 11 |
| 3 | D3 | 2D + 1 | 21 |
| 4 | D4 | 2 | 02 |
| 5 | D5 | 2D | 20 |
| 6 | D6 | 2D + 2 | 22 |
| 7 | D7 | D + 2 | 12 |
| 8 | D8 | 1 | 01 |
Now that we have found at least one primitive polynomial with which to define multiplication in our finite field, let us turn our attention to determining the multiplicative inverses of each non-zero element in our set. For convenience, since the table is directly above, let's use 122 as our primitive polynomial.
Since each polynomial maps to an integer power of D and since D8 is 1, we can use the fact that two polynomials are multiplicative inverses if the exponents in their exponential representations add to 8. Hence
Multiplicative Inverses in GF(32) mod 112
| k | Dk | Polynomial | Symbol | (Dk)-1 | Polynomial | Symbol |
| 0 | D0 | 1 | 01 | D8 | 1 | 01 |
| 1 | D1 | D | 10 | D7 | D + 2 | 12 |
| 2 | D2 | D + 1 | 11 | D6 | 2D + 2 | 22 |
| 3 | D3 | 2D + 1 | 21 | D5 | 2D | 20 |
| 4 | D4 | 2 | 02 | D4 | 2 | 02 |
| 5 | D5 | 2D | 20 | D3 | 2D + 1 | 21 |
| 6 | D6 | 2D + 2 | 22 | D2 | D + 1 | 11 |
| 7 | D7 | D + 2 | 12 | D1 | D | 10 |